/*	$Id: log.c,v 1.3 2006/03/15 03:49:16 jfb Exp $	*/
/*
 * Copyright (c) 2007 Jean-Francois Brousseau <phrakt@gmail.com>
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 *
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. The name of the author may not be used to endorse or promote products
 *    derived from this software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES,
 * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY
 * AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL
 * THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
 * EXEMPLARY, OR CONSEQUENTIAL  DAMAGES (INCLUDING, BUT NOT LIMITED TO,
 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS;
 * OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
 * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
 * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
 * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */

#include <sys/param.h>

#include <errno.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <syslog.h>
#include <pthread.h>

#include <canopy/log.h>
#include <canopy/mem.h>
#include <canopy/queue.h>
#include <canopy/string.h>

#include "fnv.h"
#include "htab.h"
#include "private.h"


struct cnp_hash_entry {
	void                        *he_data;
	void                        *he_key;
	size_t                       he_klen;
	TAILQ_ENTRY(cnp_hash_entry)  he_link;
};

struct cnp_hash_bucket {
	int                           hb_count;
	TAILQ_HEAD(, cnp_hash_entry)  hb_list;
};

struct cnp_hash_table {
	int            ht_size;
	int            ht_flags;
	int            ht_bktcnt;		/* bucket count */

	int          (*ht_keycmp)(const void *, size_t, const void *, size_t);
	unsigned int (*ht_keyhash)(const void *, size_t);

	struct cnp_hash_bucket  *ht_buckets;
	pthread_rwlock_t         ht_rwlock;

};



static struct cnp_hash_entry*  cnp_htab_getent (cnp_htab_t *, const void *,
						size_t);

static int cnp_htab_keycmp_def (const void *, size_t, const void *, size_t);
static unsigned int cnp_htab_keyhash_def (const void *, size_t);

/*
 * cnp_htab_alloc()
 *
 * Allocate a new hash table of size <size>.
 * Returns a pointer to the new hash table on success, or NULL on failure.
 */
cnp_htab_t*
cnp_htab_alloc(int size, int flags,
    int (*keycmp)(const void *, size_t, const void *, size_t),
    unsigned int (*keyhash)(const void *, size_t))
{
	int i;
	cnp_htab_t *htab;

	if ((htab = cnp_malloc(sizeof(*htab))) == NULL) {
		cnp_log(cnp_logchan, CNP_LOG_ERRNO,
		    "failed to allocate hash table");
		return (NULL);
	}

	htab->ht_size = size;
	htab->ht_bktcnt = 1 << size;

	if (keycmp != NULL)
		htab->ht_keycmp = keycmp;
	else
		htab->ht_keycmp = cnp_htab_keycmp_def;

	if (keyhash != NULL)
		htab->ht_keyhash = keyhash;
	else
		htab->ht_keyhash = cnp_htab_keyhash_def;

	if ((htab->ht_buckets = cnp_malloc(sizeof(struct cnp_hash_bucket) *
	    htab->ht_bktcnt)) == NULL) {
		cnp_log(cnp_logchan, CNP_LOG_ERRNO,
		    "failed to allocate hash table buckets");
		cnp_free(htab);
		return (NULL);
	}

	if (pthread_rwlock_init(&htab->ht_rwlock, NULL) != 0) {
		cnp_log(cnp_logchan, CNP_LOG_ERR,
		    "failed to initialize hash table read-write lock");
		cnp_htab_free(htab);
		return (NULL);
	}

	for (i = 0; i < htab->ht_bktcnt; i++) {
		htab->ht_buckets[i].hb_count = 0;
		TAILQ_INIT(&htab->ht_buckets[i].hb_list);
	}

	return (htab);
}

/*
 * cnp_htab_free()
 *
 * Free the hash table <htab> and all associated resources.  No further
 * operations may be performed on the handle after this call.
 */
void
cnp_htab_free(cnp_htab_t *htab)
{
	int i;
	struct cnp_hash_entry *ent;

	if (htab->ht_buckets != NULL) {

		/* empty all the buckets */
		for (i = 0; i < htab->ht_size; i++) {
			while (!TAILQ_EMPTY(&htab->ht_buckets[i].hb_list)) {
				ent = TAILQ_FIRST(&htab->ht_buckets[i].hb_list);
				TAILQ_REMOVE(&htab->ht_buckets[i].hb_list, ent,
				    he_link);

				cnp_free(ent->he_key);
				cnp_free(ent);
			}
		}

		cnp_free(htab->ht_buckets);
	}

	(void)pthread_rwlock_destroy(&htab->ht_rwlock);

	cnp_free(htab);
}

/*
 * cnp_htab_insert()
 *
 * Insert the object located at address <data> in the hash table <htab> with
 * the associated key <key>, which is <klen> bytes long.
 * Returns 0 on success, or -1 on failure.
 */
int
cnp_htab_insert(cnp_htab_t *htab, void *data, const void *key, size_t klen)
{
	int ret;
	unsigned int hash;
	struct cnp_hash_entry *ent;

	if ((ent = cnp_malloc(sizeof(*ent))) == NULL) {
		cnp_log(cnp_logchan, CNP_LOG_ERRNO,
		    "failed to allocate hash table entry");
		return (-1);
	}

	ent->he_data = data;
	ent->he_klen = klen;
	if ((ent->he_key = cnp_malloc(klen)) == NULL) {
		cnp_log(cnp_logchan, CNP_LOG_ERRNO,
		    "failed to allocate hash table entry");
		cnp_free(ent);
		return (-1);
	}
	memcpy(ent->he_key, key, ent->he_klen);

	if ((ret = pthread_rwlock_wrlock(&htab->ht_rwlock)) != 0) {
		cnp_log(cnp_logchan, CNP_LOG_ERR,
		    "failed to obtain write lock on hash table");
		cnp_free(ent->he_key);
		cnp_free(ent);
		return (-1);
	}

	hash = (*htab->ht_keyhash)(key, klen) % htab->ht_bktcnt;

	TAILQ_INSERT_TAIL(&htab->ht_buckets[hash].hb_list, ent, he_link);
	htab->ht_buckets[hash].hb_count++;

	if ((ret = pthread_rwlock_unlock(&htab->ht_rwlock)) != 0) {
	}

	return (0);
}

/*
 * cnp_htab_lookup()
 *
 */
void*
cnp_htab_lookup(cnp_htab_t *htab, const void *key, size_t klen)
{
	int ret;
	void *obj = NULL;
	struct cnp_hash_entry *ent;

	if ((ret = pthread_rwlock_rdlock(&htab->ht_rwlock)) != 0) {
		cnp_log(cnp_logchan, CNP_LOG_ERR,
		    "failed to obtain read lock on hash table");
		return (NULL);
	}

	if ((ent = cnp_htab_getent(htab, key, klen)) != NULL)
		obj = ent->he_data;

	if ((ret = pthread_rwlock_unlock(&htab->ht_rwlock)) != 0) {
	}

	return (obj);
}

/*
 * cnp_htab_delete()
 *
 */
int
cnp_htab_delete(cnp_htab_t *htab, const void *key, size_t klen)
{
	int ret;
	unsigned int hash;
	struct cnp_hash_entry *ent;

	if ((ret = pthread_rwlock_wrlock(&htab->ht_rwlock)) != 0) {
		cnp_log(cnp_logchan, CNP_LOG_ERR,
		    "failed to obtain write lock on hash table");
		return (-1);
	}

	if ((ent = cnp_htab_getent(htab, key, klen)) != NULL) {
		hash = (*htab->ht_keyhash)(key, klen) % htab->ht_bktcnt;
		TAILQ_REMOVE(&htab->ht_buckets[hash].hb_list, ent, he_link);
		htab->ht_buckets[hash].hb_count--;

		cnp_free(ent->he_key);
		cnp_free(ent);
	}

	if ((ret = pthread_rwlock_unlock(&htab->ht_rwlock)) != 0) {
	}

	return (0);

}

/*
 * cnp_htab_getent()
 *
 */
static struct cnp_hash_entry*
cnp_htab_getent(cnp_htab_t *htab, const void *key, size_t klen)
{
	int ret;
	unsigned int hash;
	struct cnp_hash_entry *ent;

	hash = (*htab->ht_keyhash)(key, klen) % htab->ht_bktcnt;

	TAILQ_FOREACH(ent, &htab->ht_buckets[hash].hb_list, he_link) {
		ret = (*htab->ht_keycmp)(ent->he_key, ent->he_klen, key, klen);
		if (ret == 0)
			return (ent);
	}

	return (NULL);
}

/*
 * cnp_htab_keyhash_def()
 */
static unsigned int
cnp_htab_keyhash_def(const void *key, size_t klen)
{
	return cnp_fnv32_hash(key, klen, FNV1_32_INIT);
}

/*
 * cnp_htab_keycmp_def()
 */
static int
cnp_htab_keycmp_def(const void *k1, size_t k1len, const void *k2,
    size_t k2len)
{
	if (k1len > k2len)
		return (1);
	else if (k2len > k1len)
		return (-1);
	else
		return memcmp(k1, k2, MIN(k1len, k2len));
}
